package Sort;

import java.util.Arrays;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}22:03
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {4,10,3,5,1,2};
        heap_sort(arr,arr.length);
        System.out.print(Arrays.toString(arr));
    }

    public static void build_heap(int arr[],int n){//将整个树进行一个堆顶化，先从下面的来
        int last_node = n - 1;
        int parentNode = (last_node - 1) / 2;//从下往上进行堆排序
        for (int i = parentNode; i >= 0; i--){
            heapfiy(arr,n,i);
        }
    }

    public static void heap_sort(int arr[],int n){
        build_heap(arr,n);
        for (int i = n -1; i >= 0; i--){
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            heapfiy(arr,i,0);//破环了大顶堆，顶上的数为最小所以直接用顶上的数来进行排
        }
    }

    /**
     * 堆顶化
     * @param arr 数组
     * @param n 数组长度
     * @param i 数组进行对顶化的起始坐标
     */
    public static void heapfiy(int[] arr,int n,int i){
        if ( i >= n){
            return;
        }
        int max = i;
        int left = 2*i+1;
        int right = 2*i+2;
        if (left < n && arr[left] > arr[max]){
            max = left;
        }
        if (right < n && arr[right] > arr[max]){
            max = right;
        }
        if (max != i){
            int temp = arr[max];
            arr[max] = arr[i];
            arr[i] = temp;
            heapfiy(arr,n,max);//继续往下走进行下一次比较
        }
    }
}
